Computer-aided techniques are known to include Computer-Aided Design or CAD, which relates to software solutions for authoring product design. Similarly, CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM stands for Computer-Aided Manufacturing and typically includes software solutions for defining manufacturing processes and operations.
A number of systems and programs are offered on the market for the design of objects (or parts) or assemblies of objects, forming a product, such as the one provided by Dassault Systemes under the trademark CATIA. These CAD systems allow a user to construct and manipulate complex three dimensional (3D) models of objects or assemblies of objects. CAD systems thus provide a representation of modeled objects using edges or lines, in certain cases with faces. Lines or edges may be represented in various manners, e.g. non-uniform rational B-splines (NURBS). These CAD systems manage parts or assemblies of parts as modeled objects, which are mostly specifications of geometry. Specifically, CAD files contain specifications, from which geometry is generated, which in turn allow for a representation to be generated. Geometry and representation may be stored in a single CAD file or multiple ones. CAD systems include graphic tools for representing the modeled objects to the designers; these tools are dedicated to the display of complex objects—the typical size of a file representing an object in a CAD system being in the range of one Megabyte per part, and an assembly may comprise thousands of parts. A CAD system manages models of objects, which are stored in electronic files.
Also known are Product Lifecycle Management (PLM) solutions, which refer to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise. By including the actors (company departments, business partners, suppliers, Original Equipment Manufacturers (OEM), and customers), PLM may allow this network to operate as a single entity to conceptualize, design, build, and support products and processes.
Some PLM solutions make it for instance possible to design and develop products by creating digital mockups (a 3D graphical model of a product). The digital product may be first defined and simulated using an appropriate application. Then, the lean digital manufacturing processes may be defined and modeled.
The PLM solutions provided by Dassault Systemes (under the trademarks CATIA, ENOVIA and DELMIA) provides an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.
Such PLM solutions comprise a relational database of products. The database comprises a set of textual data and relations between the data. Data typically include technical data related to the products said data being ordered in a hierarchy of data and are indexed to be searchable. The data are representative of the modeled objects, which are often modeled products and processes.
Product lifecycle information, including product configuration, process knowledge and resources information are typically intended to be edited in a collaborative way and in a dynamic way. For this reason notably, modeled objects are intended to be modified a certain number of times after they have been first created.
Any 3D object that is supposed to fit user defined specifications can be simulated through a virtual part. The virtual part is created by the designer using standard modeling features (extrude, revolute, cut, round etc.) or standard surfacing features (sweep, blend, loft, fill, deform, smoothing etc.). Many CAD systems supporting such modeling functions are history based system. This means that the creation history of design features is saved through an acyclic data flow linking the said features together through input and output links.
The history based modeling paradigm is well known since the beginning of the 80's. A solid part is described by two persistent data representations: history and B-rep (i.e. boundary representation). The B-rep is the result of the computations defined in the history. The shape of the part displayed on the screen of the computer is (a tessellation of) the B-rep. The history of the part is the design intent. Basically, the history gathers the information on the operations which the modeled object has undergone. The B-rep is generally saved together with the history because it is not possible to display complex parts only from the history data. The history is saved together with the B-rep in order to allow design changes of the part according to the design intent.
Another advantage of history based paradigm is for a designer to prepare reusable models. Indeed, other designers can reuse models by changing parameters of the history and letting the system update the new part. Since the update leads to the same result as running again the history with the new parameters, the new part is intrinsically compliant with the new design intent.
In such a context, the speed at which the update is performed is of matter, all the more for complex parts or for applications where many modifications are performed. Several technologies of the prior art for updating the part have been disclosed and are discussed below.
A very popular method to update the shape of a modeled object of which history has been modified is the following. First of all, during the creation phase, all intermediate results of the history are saved. A modification is typically for the designer to change the parameters of a feature, in other words, to change the data of a leaf node of the history. In this case, updating is for the system to replay all operations by following the input-output links from the modified leaf node down to the root node. This method holds as well for a multi-root data flow and when several leaf nodes are modified in one shot. Maystrovsky's U.S. Pat. No. 5,850,535 “Roll-back regeneration in a computer-aided design system” typically describes this technology in the particular case of a linear feature list. This update technology features two drawbacks. Firstly, the update time is closely related to the structure of the history (whether it is a linear list or a well balanced tree for example). In many low end CAD systems, the history is a linear list and its structure is out of the designer's reach. In this case, the update time is proportional to the age of the modified feature. When the history structure is controlled by the user, it is an additional difficulty for the user to balance the said history structure while designing a complex part. An inexperienced designer cannot perform this double task. The second drawback is that many operations are recomputed only because they are on the path (from the modified leaf node down to the root node) while they do not influence the resulting solid. In other words, many operations on the update path are spatially far from the actual change. Deciding whether an operation is meaningful or not during the update is a difficult question. As a consequence, the update is slow.
Another update method is to replay all operations of the history. It avoids intermediate results storage, thus saving memory. Some CAD systems used this method in the early 80's, but it is marginally used nowadays. Replaying the whole history after a modification results in an update time that is proportional to the global complexity of the part and not to the complexity of the modification. The designer expects a “simple” change to be updated faster that a “big” change. This behavior is undesirable from the designer's point of view. As a consequence, the update is slow.
Chin's U.S. Pat. No. 7,313,504 “Model management technology using feature chains” does not require history storage. Persistent data are solid primitives together with their respective “scopes” from which the algorithm dynamically generates a transient history structure. Then, the algorithm traverses this structure to compute the new part after a primitive creation or modification. This technology rebuilds a history structure each time the part is modified. Consequently, the update process requires a computation time that is proportional to the number of primitives and not to the complexity of the modification. A very simple modification would require the same amount of computation than a complex modification, which is not optimal from the designer's point of view. As a consequence, the update is slow.
In yet another technology for updating models based on history, all leaf nodes are solids, and all operations are pure Boolean operations (which are union, subtraction, intersection as opposed to non Boolean operations such as round, fillet, draft angle, tweak, thickness, shell). Given a modification intent, for example changing the size or position of a leaf solid, there exists, by theorem, a 3D volume outside which the resulting solid is invariant. This is the “a priori localization volume”. In many cases, this knowledge allows a faster update by simplifying the shape of leaf solids that are spatially far from the change, thus performing trivial or simpler operations to compute the new solid. This technology is inspired by the research paper “A null-object detection algorithm for constructive solid geometry” by R. B. Tilove, Communication of the ACM, July 1984, vol. 27, No 7. This technology features two drawbacks. Firstly, it does not take into account non Boolean operations such as draft angle, round, fillet, shell and thickness which are very popular in mechanical design. The reason is that it is impossible to anticipate how a round (or fillet, draft angle, shell, thickness) will proliferate on the solid due to tangency propagation, which eliminates the a priori localization volume. This restriction to pure Boolean operations is a major drawback in mechanical design and in solid modeling in general because a real life part always features some non Boolean characteristics (round, fillet, shell etc.). Secondly, even in the pure Boolean case, there are examples when this technology is not efficient. Consider for example the solid S=(X+Y)+Z illustrated on FIG. 1 and defined by three primitives X,Y,Z and a linear history tree involving union operations only. Let Y′ be the new version of Y, meaning that the modification intent is to replace Y with Y′. According to this technology, the best possible localization volume is V=(Y′−Y)+(Y−Y′), as illustrated on FIG. 2. The principle is to write the modified solid S′=(X+Y′)+Z as S′=(S′−V)+(S′·V)=(S−V)+(S′·V), which is illustrated on FIG. 3. The first step of the updating process is to compute the B-rep of the invariant portion of the resulting solid S′ which is S−V. Then, the history tree of the changed portion of the solid is S′·V=((X+Y′)+Z)·V. Since this formula is equal to (((X·V)+(Y′·V))+(Z·V)), all primitives α such that α·V=φ are eliminated from the expression of S′·V, which hopefully yields a reduced history tree. Finally, the updating process computes the B-rep of the solid corresponding to the reduced history tree and merges this B-rep to the B-rep of the invariant portion S−V, which yields the B-rep of the modified solid. Applied to the primitives illustrated in FIGS. 1-3, it is clear that this does compute the operation +Z because primitive Z overlaps volume V, although it is obviously not necessary to compute the operation +Z. As a consequence, the update is slow, all the more when there are non-Boolean operations in the history.
B-rep modeling is an alternate technology to history based modeling. B-rep modeling does not save the history of the part. Thus, a change is directly and locally performed on the B-rep, by deleting, moving, extrapolating, healing faces, which is very fast compared to history replay. B-rep modeling technology provides a very fast update because there is no history to replay. The first drawback is a lack of semantic. The design intent expressed through the history is lost, and reusing predefined models is not possible. Secondly, not all topological and geometrical changes are possible through B-rep modeling. Finally, a very useful integrity property of history based modeling is that the new part is equal to the part created from scratch with new inputs. B-rep modeling does not guarantee this property. In this technology, there is no need for an update method because the modifications on the model dynamically update it. However, as no information on the operations which the object has undergone is kept, a subsequent modification is actually difficult for the user. Furthermore, B-rep modeling has geometrical and topological restrictions which lead designers to often prefer history based modeling.
Kripac's patent application US2007/0291028 “fast interactive object manipulation” describes a method for real time update of a history based solid. Given the solid primitive to be modified, the algorithm computes a reduced history tree. This reduced history tree is balanced in such a way that the modified primitive is involved in the very last of the last but one operation and is combined to one or two constant solids. The reduced history tree is obtained through algebraic manipulations of the initial history tree. The B-rep representation of the constant solids is computed from scratch. Then, the (hopefully) real time update can start upon user defined changes of the solid primitive. Only interactive manipulation is addressed by this technology, nothing is said about how the modified solid is actually computed for repository purpose. Kripac's algorithm is not compatible with intermediate results saving as described earlier because the history tree is rebalanced for each modification. Beyond the computer time required for algebraic manipulations, the geometrical and topological complexity of the constant solids involved in the reduced history tree is comparable to the complexity of the whole solid. Given that the constant solids are computed from scratch, the consequence is that the reduced history tree step is almost as costly as computing the whole solid from scratch. As a consequence, before the real time capability is available, the designer must wait during a time period that is generally too long. Furthermore, there exists a failure risk because algebraic manipulations may duplicate primitives in the reduced history tree, which causes tangent or locally identical surfaces situations. It is well known that these situations are handled with enormous difficulty by geometrical modelers. Furthermore, the integrity of the data model is not guaranteed because the computation performed by the system to provide the modified solid is totally different from the computation performed to create the solid from the modified primitives through the initial history. As previously mentioned, only interactive manipulation is addressed by this technology. How the final solid is computed before repository saving may need further computation. Drawbacks are thus a costly preprocessing and a potential geometrical fragility. As a consequence, the update is slow.
Solidworks' patent application WO2008/127254 describes a method for “locally updating a three dimensional model”. Given a solid defined by a feature list and the corresponding B-rep and given a modified feature, the method determines a subset of features that possibly affect the shape of the solid. These features are related to the modified feature through three kinds of relationships: parent/child relationship, topological adjacency and spatial intersection. Then, topological faces of these features that appear on the solid are removed and/or replaced by faces of modified features. This method is directed to the general case including Boolean (union, subtraction, intersection) and non Boolean operations (round, fillet, draft, thickness, shell etc.). The resulting solid is the same as the solid obtained by regenerating all features from scratch. The first drawback is that in some cases, features are recomputed despite they do not change the resulting solid. The second drawback is that the computing path followed by the system to update the solid is totally different from the computing path to generate the modified solid from scratch. The update performs new computations to get the modified solid, other computations than those performed through a traditional update. For instance, according to page 12, line 11 of WO2008/127254 and referring again to FIGS. 1-3: a “spatial intersection relationship” is identified between the modified feature Y and Z with causes the +Z operation to be replayed, although unnecessary. As a consequence, the update speed can still be increased.
Besides, it has to be noted that graph theory has been discussed in the context of model modification.
The article entitled “On the use of graph transformation for model refactoring” by T. Mens, of the University of Mons-Hainaut, in Belgium, relates to model refactoring, and shows how graph transformation can provide formal support for this activity.
The article entitled “Scenario integration via higher-order graphs”, in Technical report No. 2006-517, by Z. Diskin, J. Dingel, H. Liang, from Queen's University, in Kingston, Ontario, Canada, 2006, also presents the use of graph theory for the management of scenarios involving models.
On graph theory specifically, the thesis entitled “A relation-algebraic approach to graph structure transformation”, by W. Kahl, from McMaster University in Ontario, Canada (most of the work completed at the Institute for Software Technology of Universität der Bundeswehr München in Germany), 2002, includes a statement about “the categoric approach to graph transformation”. It explains basic categorical push-out and pull-back operations as well as the “double push-out” graph rewriting.
However, there still exists a need for improving the update of a modeled object.